#include <iostream>
#include <vector>
#include <string>
using namespace std;

string strs[10] = { "123","123","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
vector<string> ret;
string path;
vector<string> letterCombinations(string digits) {
    if(digits.size()>0)
        dfs(digits, 0);

        return ret;
    }

void dfs(string s, int pos)
    {
        if (pos == s.size())
        {
            ret.push_back(path);
            return;
        }

        int n = s[pos] - '0';
        for (char ch : strs[n])
        {
            path.push_back(ch);
            dfs(s, pos + 1);
            path.pop_back();
        }
}